package 我的Java学习_算法基础.day_08;

/**
 * @author 挚爱之夕
 * @date 2021/8/26 - 08 - 26 - 12:54
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _136_完全背包问题 {
    public static void main(String[] args) {
        int n = dynamicPlanning();
        System.out.println(n);
    }
    static int[] weights = {2,3,3,2}; //质量数组
    static int[] values = {3,2,4,2};  //价值数组
    static int n = 4 ; //物品数量
    static int capacity = 11;

    private static int dynamicPlanning (){
        int[][] dp = new int[n][capacity +1];
        //初始化dp表的第一行
        for (int j = 0; j < capacity + 1; j++) {
            int count = j/weights[0];
            if(count>0){
                dp[0][j] = count*values[0];
            }
        }
        //其他行
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < capacity + 1; j++) {
                if(j>=weights[i]){
                    int i1 = values[i] + dp[i][j - weights[i]];//选择1个当前物品
                    int i2 = dp[i - 1][j];  //不选
                    dp[i][j] = Math.max(i1,i2);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n-1][capacity];
    }
}
